#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <cmath>
#include "mpi.h"


using namespace std;

const int MAX = 10;

struct PathF
{
  bool exist;
  int weight;
  vector <unsigned int> path;

  PathF()
  {
    exist   = false;
    weight  = 0;
  }
};

class Graph
{
  int N;        // Nodes
  int P;        // Pathes 

  public:
  int G[MAX][MAX];    // Adjacency matrix of not complete graph
  PathF ** Gf;  // Adjacency matrix of complet graph 
  Graph();
  Graph(char * nazwa);
  ~Graph();

  void allocation();
  void deallocation();
  bool isData();
  bool read(char * filename);
  void compute();
  void floydWarshall(int my_rank, int chunk);
  void findPaths();
  void findPath(int start, int meta);
  vector<int> antecedents(int x);
  void show();
  void showFull();
  void showShortesPaths();
  int getN() { return N; }
  int setN(int n) { N = n; }  
};

Graph::Graph()
{
  P = 0;
  N = 0;
}

Graph::Graph(char * filename)
{
  N = 0;
  P = 0;
  read(filename);
}

Graph::~Graph()
{
//  deallocation();
}

void Graph::allocation()
{
//  G = new int * [N];
  Gf = new PathF * [N];

  for (int i = 0; i < MAX; i++) {
    for (int j = 0; j < MAX; j++) {
      G[i][j] = -1;	//path doesn't exist by default
    }
  }

  for (int i = 0; i < N; ++i)
  {
//    G[i] = new int[N];
    Gf[i] = new PathF[N];

    // Diagonal
    G[i][i] = 0;	// exists, but the weight is 0
    Gf[i][i].exist = true;
  }
}

void Graph::deallocation()
{
  if ( isData() )
  {
  printf("dealokacja\n");
    for ( int i = 0; i < N; ++i )
    {
      delete [] G[i];
      delete [] Gf[i];
    }

    delete [] G;
    delete [] Gf;
  }
}

bool Graph::isData()
{
  if ( N > 0 )  return true;
  else          return false;
}

/* Method to reading data from file.
 * File structure:
 * nodes  paths
 * from to  weight
 *
 * Example:
 * 2  1
 * 0  1 10
 *
 * Means that graph has two nodes, and one path
 * from node 0 to node 1 and this path has weight
 * equal 10.
 */
bool Graph::read(char * filename)
{
  ifstream file(filename, ifstream::in);
  
  if ( file.is_open() )
  {
    file >> N >> P;

    allocation();
    printf("N: %d\n", N);
    
    // Reading file
    int x, y, w;	// tmp vars
    
    for (int i = 0; i < P; ++i)
    {
      file >> x >> y >> w;
      G[x - 1][y - 1] = w;

      Gf[x - 1][y - 1].exist = true;
      Gf[x - 1][y - 1].weight = w;
    }

    return true;
  }
  return false;
}

// Finding all-pairs shortest paths on a graph
void Graph::floydWarshall(int my_rank, int chunk)
//every process makes only a chunk of computations

{
  for ( int k = 0; k < N; ++k )
  {
    for ( int i = my_rank*chunk; i < (my_rank*chunk)+chunk && i < N; ++i )
    {
      for ( int j = 0; j < N; ++j )
      {
        if ( G[i][k] > -1 && G[k][j] > -1 )
        {
          if ( G[i][j] == -1 )
          {
            G[i][j] = G[i][k] + G[k][j];
          }
          else
          {
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
          }
//          Gf[i][j].exist = true;
        }
      }
    }
  }
}

void Graph::findPaths()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      findPath(i, j);
    }
  }
}

void Graph::findPath(int start, int meta)
{
  if ( !Gf[start][meta].exist )
  {
    return;
  }

  vector<int> ant;    // Antecedents
  stack<int> path;  // Path from start to meta
  int u, v;         // Tmp vars

  path.push(meta);
  v = meta;

  while ( v != start )
  {
    ant = antecedents(v);

    if ( ant.empty() )
    {
      break;
    }

    for ( unsigned int i = 0; i < ant.size(); ++i )
    {
      if ( Gf[start][v].weight == Gf[start][ant[i]].weight + G[ant[i]][v] )
      {
        u = ant[i];
      }
    }

    path.push(u);
    v = u;
  }

  // Copy stack to path in PathF structure
  while ( !path.empty() )
  {
    Gf[start][meta].path.push_back(path.top());
    path.pop();
  }
}

vector<int> Graph::antecedents(int x)
{
  vector<int> ants;

  for ( int i = 0; i < N; ++i )
  {
    if ( G[i][x] > 0)	// -1: does not exist, 0: path to itself
    {
      ants.push_back(i);
    }
  }

  return ants;
}

void Graph::show()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      cout << G[i][j] << " ";
    }

    cout << endl;
  }
}

void Graph::showFull()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      cout << Gf[i][j].weight << " ";
    }

    cout << endl;
  }
}

void Graph::showShortesPaths()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      if ( i != j )
      {
        cout << "Shortes path from: " << i << " to: " << j << " weight: " << Gf[i][j].weight << ". Path: ";

        for ( unsigned int k = 0; k < Gf[i][j].path.size(); ++k )
        {
          cout << Gf[i][j].path[k] << ", ";
        }

        cout << endl;
      }
    }
  }
}

int main(int argc, char * argv[])
{
  int my_rank, size;
  int chunk, n;
  int source, dest;
  int tag=50;
  MPI_Status status;
  MPI_Datatype rowtype;

//inicjacja MPI, pobranie swojej rangi i rozmiaru komunikatora (ilosci procesow)
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);

  if ( argc == 1 )
  {
    cout << "Give path to file with graph" << endl;
    cout << "Example:" << endl;
    cout << argv[0] << " dane_przykladowe.txt" << endl;

    exit(0);
  }

// proces root tworzy graf na podstawie danych z pliku  
  Graph G(argv[1]);
  n = G.getN();
  MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
//  Graph Gr;
//pozostale procesy alokuja miejsce na graf
  if(my_rank != 0) {
    G.setN(n);
//    G.allocation();  
  }

// tworzymy nowy typ
  MPI_Type_contiguous(n, MPI_INT, &rowtype);
  MPI_Type_commit(&rowtype);
  
// rozsylamy wypelniona macierz do wszystkich procesow za pomoca nowego typu
  MPI_Bcast(G.G, n, rowtype, 0, MPI_COMM_WORLD);
/*  cout << "rank: " << my_rank << endl;
  G.show();
  cout << endl << endl;
*/
 
//obliczamy po ile wierszy bedzie obliczac kazdy proces
  chunk = ceil((double)n/(double)size); //  printf("chunk: %d\n", chunk);
        
// wywolujemy algorytm na czesci macierzy odpowiadajacej procesowi
  G.floydWarshall(my_rank, chunk);

  MPI_Barrier(MPI_COMM_WORLD);
  printf("my rank: %d\n", my_rank);
//  if (my_rank == 1) {
//    G.show();
//    cout << endl << endl;
//  }
//kazdy proces odsyla swoja czesc
  if(my_rank != 0) {
    dest = 0;
//    printf("my rank: %d\n", my_rank);
    MPI_Send(&G.G[my_rank*chunk][0], chunk, rowtype, dest, tag, MPI_COMM_WORLD);  
  }  
//proces root odbiera i przepisuje z G do Gf i wykonuje:
  else {
    int tmp[100]; // = new int[n*chunk];
    for (source=1; source<size; source++) {
      MPI_Recv(tmp, chunk, rowtype, source, tag, MPI_COMM_WORLD, &status);
      int k = 0;
      for (int i = chunk*source; i < (chunk*source)+chunk; i++) {
        for (int j = 0; j < n; j++) {
//          printf("%d ", tmp[k]);
          G.Gf[i][j].weight = G.G[i][j] = tmp[k++];
          
          if (G.G[i][j] > -1) {
            G.Gf[i][j].exist = true;
          }
          else G.Gf[i][j].exist = false;
        }
      }
    }

//    delete [] tmp;

    G.findPaths();
    G.show();
    G.showShortesPaths();
  }

  return 0;
}
